#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

//#define USE_ZERO_SPACE //使用list[0]作为辅助空间,不使用则将此行注释即可

static void show(sqlist list, int n)
{
#ifdef USE_ZERO_SPACE
        for (int i = 1; i < n; i++)
                printf("%d ", list[i]);
        printf("\n");
#else
        for (int i = 0; i < n; i++)
                printf("%d ", list[i]);
        printf("\n");
#endif
}

static void TableShow(Table tb, int n)
{
        printf("link域顺序为：");
        for (int i = 1; i < n; ++i)
                printf("%d ", tb[i].link);
        printf("\n");

        printf("按照link域计算的顺序为：");
        int p = 0;
        while ((p = tb[p].link) != 0)
                printf("%d ", tb[p].data);
        printf("\n");
}

int main(void)
{
#ifdef USE_ZERO_SPACE
        sqlist list = {0, 49, 38, 65, 97, 76, 13, 27, 49};
        int n = 9;
#else
        sqlist list = {49, 38, 65, 97, 76, 13, 27, 49};
        int n = 8;
#endif

//插入排序
#if 0   
        printf("插入排序前的顺序为：");
        show(list, n);
        InsertSort(list, n);
        printf("插入排序后的顺序为：");
        show(list, n);
#endif

//折半插入排序
#if 0
        printf("折半插入排序前的顺序为：");
        show(list, n);
        BInsertSort(list, n);
        printf("折半插入排序后的顺序为：");
        show(list, n);
#endif

// 2-路插入排序
#if 0
        printf("2-路插入排序前的顺序为：");
        show(list, n);
        TWayInsertSort(list,8);
        printf("2-路插入排序后的顺序为：");
        show(list, n);
#endif

//表插入排序
#if 0
        Table tb;
        tb[0].data = MAXVALUE;
        tb[0].link = 0;
        for (int i = 1; i < n; i++)
        {
                tb[i].data = list[i];
                tb[i].link = 0;
        }
        printf("表插入排序前的顺序为：");
        show(list, 9);
        TableInsertSort(tb, n);
        printf("表插入排序后的顺序为：\n");
        TableShow(tb,n);
#endif

//希尔排序
#if 0
        printf("希尔排序前的顺序为：");
        show(list, n);
        int dlta[] = {5,3,2,1};   //给出增量
        int t = sizeof(dlta) / sizeof(int);
        ShellSort(list, n, dlta, t);
        printf("希尔排序后的顺序为：");
        show(list,n);
#endif

//冒泡排序
#if 0
        printf("冒泡排序后的顺序为：");
        BubbleSort(list, n);
        show(list,n);
#endif

//快速排序
#if 0
        printf("快速排序前的顺序为：");
        show(list,n);
        int low = 0, high = n - 1;
        QuickSort(list,low,high);
        printf("快速排序后的顺序为：");
        show(list,n);
#endif

//简单选择排序
#if 0
        printf("简单选择排序前的顺序为：");
        show(list,n);
        SelectSort(list, n);
        printf("简单选择排序后的顺序为：");
        show(list,n);
#endif

//树形选择排序
#if 0
        printf("树形选择排序后的顺序为：");
        TreeSelectSort(list, n);
        show(list,n);
#endif

//堆排序
#if 1
        printf("堆排序后的顺序为：");
        HeapSort(list, n);
        show(list,n);
#endif

//归并排序
#if 0
        printf("归并排序后的顺序为：");
        sqlist tmp;   //辅助数组
        MergeSort(list, tmp, 0, n - 1);
        show(list,n);
#endif

//基数排序
#if 0
        sqlist L = {278, 109, 63, 930, 589, 184, 505, 269, 8, 83};
        n = 10;
        printf("基数排序后的顺序为：");
        RadixSort(L, n);
        show(L, n);
#endif

        exit(EXIT_SUCCESS);
}
